This invention relates generally to a microprogram control system, and more particularly to a processor of microprogram control for pipeline processing including a branch microinstruction.
Microprogram control systems have been used as a control system of microprocessors. In the microprogram control system, an operation code inputted from outside is decoded by an instruction decoder, the result is transferred to a memory storing therein a microinstruction, and a microinstruction sequence is acutated. Among the microprogram control systems, a system which stores the microinstruction in a ROM (Read Only Memory) inside a chip is known. A system in which the content of the address defined by a microprogram counter is fetched from ROM, decoded and executed is known. In such a case, the basic form in which fetch, decode and execution of the microinstruction and fetch of a next microinstruction are carried out in the order named is referred to as "sequential control". In contrast, a form in which a microinstruction to be executed in future is anticipated in parallel with the execution of a current instruction and the microinstruction to be executed in the future is prefetched is referred to as "advance control".
A form in which a plurality of programs are parallel processed at the same point of time is referred to as "multi-processing".
A processing method which subjects a plurality of instructions to simultaneous advance control and to parallel processing or in other words, which simultaneously effects advance control and multi-control in exactly the same way as in a belt conveyor system, is referred to as "pipeline control". In the pipeline control system, the operation of a microinstruction is divided into several stages and in the meantime, a large number of data sets are simultaneously passed so as to increase processing performance per unit time.
In processors providing pipeline control, branch control has been the problem in the past. In other words, since a plurality of cycles is necessary for the operation of one microinstruction, a speed of one instruction/one cycle has been obtained by effecting advance control and parallel processing of the microinstruction by pipeline control. However, if a branch microinstruction exists midway in the sequence, the sequence of operation of the microinstruction is disturbed. In other words, the microinstruction that has already been fetched or decoded becomes invalid, and the fetching of a target microinstruction defined by the branch instruction becomes necessary once again, and a drastic delay of the operation speed occurs.
With the improvement in the integration density of semiconductors, microprocessors using microprogram control have gained a preferred status. In such microprocessors, a microprogram control system of two-level pipeline control having lower multiplicity has often been used. In the two-level pipeline control, in each clock cycle during which a program counter represents each address of n, n+1, n+2, n+3, . . . (that is to say, when the microinstruction at each address of n, n+1, n+2, n+3, . . . is fetched), the microinstruction stored in each succeeding address, i.e., n-1, n, n+1, n+2, . . . , is being executed. Two-phase clocks .phi..sub.1 and .phi..sub.2 that do not overlap with each other are used as the operation clocks. In the pipeline control, parallel processing and advance control are effected simultaneously. For example, when the program counter represents n at the clock .phi..sub.1, the microinstruction n-1 is executed and at the same time, the microinstruction n is prefetched.
In this case, too, however, control of branch microinstructions such as jump (JMP), jump to subroutine (JSR) or return from subroutine (RTS) becomes a problem. In other words, since pipeline control is effected, the microinstruction of the next address to the branch microinstruction is executed.
It will be hereby assumed that the microinstruction at the (n+1)th address is the following branch microinstruction in the control sequence shown in FIG. 5: EQU JMP cc ADR (1)
Here, JMP is a branch instruction code, cc is a branch condition code and ADR is a target address of branch. When the branch condition is satisfied, the target address of branch ADR is loaded to the program counter and at the same time, the instruction of the (n+2)th address is executed as shown in FIG. 5. Since the instruction of the (n+2)th address is one that continues the branch instruction, it should not be executed originally, but is executed in practice. In other words, there is the problem that the microinstruction of the address next to the branch microinstruction is executed.
As means for solving this problem, Patterson et al. proposed "Delayed Jump System" (D. A. Patterson and C. H. Sequin, "A VLSI RICS", IEEE COMPUTER, Vol. 15, No. 9, pp. 8-21, Sept. 1982).
According to this delayed jump system, a NOP (No Operation) microinstruction is inserted immediately after the branch microinstruction. In other words, as illustrated in the comparison table of conditional branch instructions of FIG. 6, the two-level pipeline control is made in the sequence of MOVE X, A (move instruction) at the (n-1)th address, ADD 1, A (addition instruction) at the nth address, JUMP n+4 (branch instruction: jump to the (n+4)th address) at the (n+1)th address and ADD A, B (addition instruction) at the (n+2)th address in normal branch (normal jump: N. JUMP). At this time, the instruction ADD A, B, which is next to the instruction JUMP n+4, is also executed. In other words, if the branch condition is true, MOVE A, Z which is the instruction of the (n+4)th address should be executed after the instruction of JUMP n+4. However, the instruction ADD A, B is executed, too, in the sequence before the jump. In contrast, in the delayed jump (D. JUMP) system, the NOP instruction is always inserted after JUMP n+5 (branch instruction) of the (n+1)th address when the program is prepared. For this reason, the NOP instruction next to JUMP n+5 is executed in the case of the pipeline control. In this case, each microprogram is moved back by one address. This means that the program size becomes greater by the NOP instruction, and is not suitable from the aspect of integration density in microprocessors of one-chip type which store the microinstructions in ROM or the like.
Furthermore, in an optimized delayed jump (0. D. JUMP) system which effects optimization, the sequence of the branch microinstruction (JUMP n+4) and the instruction (ADD 1, A) immediately after the former is replaced and the NOP microinstruction is deleted. Accordingly, the microinstruction (add instruction of ADD 1, A) whose sequence is thus changed can be executed, too, by the two-level pipeline control without increasing the program size.
However, the optimized delayed jump system cannot always be used. For example, optimization cannot be made for conditional branch microinstructions in which branching is effected according to the result of calculation of the microinstruction just before, and so a NOP microinstruction just after is necessary, too. In the optimized delayed jump (O. D. JUMP) shown in FIG. 6, for example, whether or not a branch is made is determined depending upon the result of ADD 1, A (add instruction) immediately after the instruction JUMP n+4. In this case, the sequence of the branch instruction JUMP n+4 and the add instruction ADD 1, A cannot be changed, and the NOP instruction must be inserted next to the instruction JUMP n+4.
Therefore, if the branch instruction controlled by the delayed jump system is employed, a large number of NOP microinstructions are necessary for the microprogram of those microprocessors in which a large number of conditional branch microinstructions appear such as microprocessors for controlling I/O controllers, for example, so that the number of steps of the microprogram becomes greater by the number of inserted NOP instructions, the memory capacity increases and the integration density of the microprocessors drops.